% 在本地编译时，采用XeLaTeX编译，pdfLaTeX可能编译失败

\documentclass[11pt]{article}
\usepackage{geometry}
\geometry{left=2.0cm,right=2.0cm,top=2.5cm,bottom=2.5cm}

\usepackage{ctex}
\usepackage{comment}
\usepackage{booktabs}
\usepackage{graphicx}
\usepackage{diagbox}
\usepackage{amsmath,amsfonts,graphicx,amssymb,bm,amsthm}
\usepackage{algorithm,algorithmicx}
\usepackage[noend]{algpseudocode}
\usepackage{fancyhdr}
\usepackage{tikz}
\usepackage{graphicx}
\usetikzlibrary{arrows,automata}
\usepackage{hyperref}
%以下是对latex插入代码块的头文件内容
\usepackage{listings}
\usepackage{color}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
  language=Python,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=none,
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace=true,
  tabsize=3
}
%以上是对latex插入代码块的头文件内容



\setlength{\headheight}{14pt}

\newcounter{counter_exm}\setcounter{counter_exm}{1}
%\newcounter{counter_thm}\setcounter{counter_thm}{1}
%\newcounter{counter_lma}\setcounter{counter_lma}{1}
%\newcounter{counter_dft}\setcounter{counter_dft}{1}
%\newcounter{counter_clm}\setcounter{counter_clm}{1}
%\newcounter{counter_cly}\setcounter{counter_cly}{1}

\newtheorem{theorem}{\hskip 1.7em 定理}
\newtheorem{lemma}[theorem]{\hskip 1.7em 引理}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{\hskip 1.7em 命题}
\newtheorem{corollary}[theorem]{\hskip 1.7em 推论}
\newtheorem{definition}[theorem]{\hskip 1.7em 定义}

\renewcommand{\emph}[1]{\begin{kaishu}#1\end{kaishu}}

\newenvironment{solution}{{\noindent\hskip 2em \bf 解 \quad}}


\renewenvironment{proof}{{\noindent\hskip 2em \bf 证明 \quad}}{\hfill$\qed$\par}
\newenvironment{example}{{\noindent\hskip 2em \bf 例 \arabic{counter_exm}\quad}}{\addtocounter{counter_exm}{1}\par}

\newenvironment{concept}[1]{{\bf #1\quad} \begin{kaishu}} {\end{kaishu}\par}

\newcommand\E{\mathbb{E}}

% 以上是预定义宏等设置,在不熟悉LaTeX的情况下可不作修改.

% TODO: 在此处更改第X讲
\title{算法设计初步第X讲}
\usetikzlibrary{positioning}

\begin{document}

    \pagestyle{fancy}
    \lhead{\kaishu 杭州师范大学}
    \chead{}
    \rhead{\kaishu 2020年秋季学期算法设计初步}

    % TODO: 在此处更改第X讲、授课时间与记录人
    \begin{center}
        {\LARGE \bf 算法设计初步第一次上机作业}\\
    \end{center}
        \begin{kaishu}
            授课时间: 2020年10月13日\quad
            授课教师: 张仁军
            \hfill 提交人: 范吉祥
        \end{kaishu}
    
    %%%%%%%%%%%%%%%%%%%%% Your note starts from here %%%%%%%%%%%%%%%%%%%%%

    \section{作业描述}
    
    \begin{itemize}
        \subsection{题目描述}
        \item 在一个无序数组种寻找第K大的元素，例如给定数组[3,2,1,5,6,4],如果K=2，则算法输出5   
    \end{itemize}
    \section{答案}
    \begin{itemize}
        \subsection{尝试快排算法} 
        \item 尝试使用快排算法进行解决，即先进行从小到大排序，完成排序之后再选出所需要的元素
        \begin{lstlisting}
        def quick_sort(target):
            length = len(target)
            if length <= 1:
                return target
            else:
                pivot = target[0] # 取第一个数作为基准值
                left = [element for element in target[1:] if element <= pivot]#将列表中比基准数小的数字放入left列表中
                right = [element for element in target[1:] if element > pivot]#将列表中比基准数大的数字放入right列表中
                return quick_sort_pythonic(left) + [pivot] + quick_sort_pythonic(right)
            \end{lstlisting}
        \subsection{快排算法设计过程以及时间复杂度}
        \subsubsection{算法设计过程} 
        \item 将列表输入到快排算法的函数中，首先会将第一个数字作为基准值用作比较，然后将列表中比基准值小的数字放入left列表中，再将列表中比基准值大的数字放入right列表中，再将列表left和right进行同样迭代，直到每一个return的列表长度只有1，最终返回一个排好序的列表，最后输入所需要的K值
        \newpage
        \subsubsection{时间复杂度}
        \item  最佳情况：当列表长度只有1时，这个时候时间复杂度为C
        \item  平均情况：假设每次都恰巧二分，因此递推公式是$T(n)=2*T(n/2)+n$，推到可得时间复杂度为$O(nlog(n))$
        \item  最坏情况：假设这个数组已经排好了顺序，因此每次第一个元素作为基准元素的话，那么left列表中永远是空的，而right列表则永远是n-1个元素(n为元素个数)，那么算法大概要被调用n次，考虑到平均每次读取的元素为$(n-1+1)\div 2$，因此时间复杂度为$O(n^2)$
        \subsection{尝试其他可能}
        \begin{lstlisting}
            def better(a,k):
                while True:
                    if len(a)<k:
                        print('the number is out of range !')
                        return
                    a_1 = a[0]
                    k_1 = 0
                    k_2 = 0
                    B = []
                    L = []
                    for i in range(len(a)-1):
                        a_i = a[i+1]
                        if a_i<a_1:
                            L.append(a_i)
                            k_2 += 1
                        else:
                            B.append(a_i)
                            k_1 += 1
                    if k_1+1>k:
                        a = B
                    elif k_1+1==k:
                        return a_1
                    else:
                        a=L
                        k = k - k_1-1
        \end{lstlisting}
        \newpage
        \subsubsection{算法设计过程} 
        \item 将列表输入到better函数中，如果列表长度小于需求位数，则会输出'the number is out of range !'，若大于则选定列表中第一个数为基准数，并开始遍历判断，若比基准数大则将其放入L列表中，比基准数小则将其放入B列表中，同时计算两个列表的长度，然后计算B列表的长度，如果B列表的长度+1比选定为位数大，则将B列表回代，如果两个相等，则返回基准数，因为此时其正好为第K大元素，如果小于k，则将L列表进行回代，此时第K大元素在L列表中，需要减去B列表中元素的个数-1
        \subsubsection{时间复杂度}
        \item  最佳情况：当列表长度只有1时，这个时候时间复杂度为C
        \item  平均情况：假设每次正好都二分，则时间复杂度为$O(n)$
        \item  最坏情况：假设这个数组已经排好了顺序，因此每次第一个元素作为基准元素的话，那么left列表中永远是空的，而right列表则永远是n-1个元素(n为元素个数)，那么算法大概要被调用n次，考虑到平均每次读取的元素为$(n-1+1)\div 2$，因此时间复杂度为$O(n^2)$
    \end{itemize}
    


    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%% End %%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
\end{document}